package 寒假刷题;

public class 飞地的数量 {
    int m,n;
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i==0 || i==m-1 || j==0 || j==n-1) && grid[i][j]==1)
                    dfs(grid,i,j);
            }
        }
        int num = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]==1)
                    num++;
            }
        }
        return num;
    }

    private void dfs(int[][] grid, int i, int j) {
        if (i<0 || i>=m || j<0 || j>=n || grid[i][j]==0)
            return;
        grid[i][j]=0;
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}
